use std::collections::VecDeque;

#[derive(Debug)]
struct Graph {
    adjacency: Vec<Vec<usize>>,
}

impl Graph {
    fn new(size: usize) -> Self {
        Graph {
            adjacency: vec![vec![]; size],
        }
    }

    fn add_edge(&mut self, from: usize, to: usize) {
        self.adjacency[from].push(to);
    }
}

fn bfs(graph: &Graph, start: usize) -> Vec<usize> {  
    let mut visited = vec![false; graph.adjacency.len()];  
    // TODO: 使用队列实现  
    //visited  
    let mut queue = VecDeque::new();
    let mut result = vec![];

    visited[start] = true;
    queue.push_back(start);

    while let Some(node) = queue.pop_front() {
        result.push(node);
        
        // 获取邻接节点（安全索引访问）
        if let Some(neighbors) = graph.adjacency.get(node) {
            for &neighbor in neighbors {
                if neighbor < visited.len() && !visited[neighbor] {
                    visited[neighbor] = true;
                    queue.push_back(neighbor);
                }
            }
        }
    }
    result
}  

#[test] 
fn test_bfs_order() { 
    /* 验证遍历顺序 */ 
    let mut graph = Graph::new(4);
    graph.add_edge(0, 1);
    graph.add_edge(0, 2);
    graph.add_edge(1, 2);
    graph.add_edge(2, 0);
    graph.add_edge(2, 3);
    
    assert_eq!(bfs(&graph, 2), vec![2, 0, 3, 1]); // 层级遍历验证
}  

// 添加图遍历可视化
fn main() {
    let mut graph = Graph::new(5);
    graph.add_edge(0, 1);
    graph.add_edge(0, 2);
    graph.add_edge(1, 3);
    graph.add_edge(2, 4);
    
    println!("BFS traversal from node 0:");
    println!("{:?}", bfs(&graph, 0));
}